require 'yaml'

def deep_copy obj
	YAML::load(YAML::dump(obj))
end

module MinMax
	def chercher depth, maxDepth
		minMaxAlt = (depth % 2 == 1)
		
		if (depth == maxDepth) then
			points = calcPoints(minMaxAlt, grille)
			chemin = Array.new
		else
			eachCoup(minMaxAlt) do |coup|
				context = copy
				context.jouerCoup minMaxAlt, coup
				tmp_points, tmp_chemin = context.chercherRec(depth + 1, maxDepth)
				
				if (minMaxAlt and tmp_points > points) or (not minMaxAlt and tmp_points < points) then
					points = tmp_points
					chemin = tmp_chemin
					chemin << coup
				end
			end
		end
		
		return points, chemin
	end
end

module AlphaBeta
	@@infinite = 1000
	
	def chercher depth, maxDepth
		chercherRec depth, maxDepth, -@@infinite, @@infinite
	end
	
	def chercherRec depth, maxDepth, alpha, beta
		$nb_noeuds += 1 if $nb_noeuds
		minMaxAlt = (depth % 2 == 1)
		
		if (depth == maxDepth) then
			points = calcPoints(minMaxAlt)
			chemin = Array.new
		else
			if (minMaxAlt) then
				points = -@@infinite
			else
				points = @@infinite
			end
			
			eachCoup(minMaxAlt) do |coup|
				context = copy
				context.jouerCoup minMaxAlt, coup
				tmp_points, tmp_chemin = context.chercherRec(depth + 1, maxDepth, alpha, beta)
				
				if (minMaxAlt and tmp_points > points) or (not minMaxAlt and tmp_points < points) then
					points = tmp_points
					chemin = tmp_chemin
					chemin << coup
					
					if minMaxAlt then
						alpha = [alpha, points].max
						break if points >= beta
					else
						beta = [alpha, points].min
						break if alpha >= points
					end
				end
			end
		end
		
		chemin = Array.new unless chemin
		return points, chemin
	end
end

class BacteriaAI < BacteriaGrille
	attr_writer :joueur, :adversaire
	attr_reader :joueur, :adversaire
	
	include AlphaBeta
	
	def initialize width, height
		super width, height
		@depth = 5
	end
	
	def self.from_grille grille
		ngrille = BacteriaAI.new(grille.width, grille.height)
		ngrille.grille = deep_copy(grille.grille)
		
		return ngrille
	end
	
	def eachCoup minMaxAlt
		i = 0
		eachCase do |rcase, orig|
			if (rcase.is_a? CaseVide) then
				eachAround orig  do |rcase2, dest|
					if (rcase2.is_a? @joueur.class) then
						i += 1
						yield Coup.new dest, orig
						break
					end
				end
			end
			
			if (rcase.is_a? @joueur.class) then
				eachJump orig do |rcase2, dest|
					if (rcase2.is_a? CaseVide) then
						i += 1
						yield Coup.new orig, dest
					end
				end
			end
		end
		
		return i
	end
	
	def calcPoints minMaxAlt
		points = 0
		eachCase do |rcase, orig|
			if (rcase.is_a? @joueur.class) then
				points += 1
			end
		end
		
		return points
	end
	
	def jouerCoup minMaxAlt, coup
		begin
			super coup, (minMaxAlt ? @joueur:@adversaire)
		rescue Exception => e
			#~ STDERR.puts e
		end
	end
	
	def meilleurCoup
		tmp_points, tmp_chemin = chercher(1, @depth)
		return nil if tmp_chemin == []
		return tmp_chemin.last
	end
	
	def copy
		return deep_copy(self)
	end
end
